# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=15
    
    PROBLEM
    
    Starting in the top left corner of a 2×2 grid, there are 6 routes
    (without backtracking) to the bottom right corner.

    How many routes are there through a 20×20 grid?

    
    NOTES
    Reminiscent of the grains of sand on a chess board fable.
    
    REFERENCES
    
    
    PERFORMANCE
    time <function test_case at 0x7fda778756e0>: 0.000984 s
    time <function solution at 0x7fda778757d0>: 0.007465 s
"""
#
# Import
#
import time
from collections import deque


#
# Globals / Constants
#
def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected):
    assert value == expected, "value %s != expected %s" % (
        value, expected)


#
# Test Case / Solution
#
@timeit    
def test_case():
    expected = 6
    
    routes = trace_routes(2,2)
    assert_match(len(routes), expected)
    
    routes = count_routes(2,2)
    assert_match(routes, expected)
    
    assert_match(len(trace_routes(4,4)), count_routes(4,4))

    print "test case passed!"

@timeit
def solution():
    return count_routes(20, 20)
        

#
# Support Code
#
def count_routes(grid_width, grid_height):
    """start at upper corner and move left and down"""
    start_pt = (0, grid_height)
    end_pt = (grid_width, 0)
    grid = build_grid(grid_width, grid_height)
    
    # build grid map (grid map can be said to track different possible routes
    # at each point)
    grid_map = dict()
    for pt in grid:
        grid_map[pt] = 0
    grid_map[start_pt] = 1
    
    # walk routes updating grid map
    routes = [start_pt]
    
    # function to check completion
    def at_end_pt(routes):
        return routes == [end_pt]
    
    # from each point, move to new points and update grip_map score
    while not at_end_pt(routes):
        next_steps = []
        
        for current_pt in routes:
            right_pt = move_right(current_pt)
            down_pt = move_down(current_pt)
            
            if right_pt in grid:
                grid_map[right_pt] += grid_map[current_pt]
                if right_pt not in next_steps:
                    next_steps.append(right_pt)
                
            if down_pt in grid:
                grid_map[down_pt] += grid_map[current_pt]
                if down_pt not in next_steps:
                    next_steps.append(down_pt)
                    
        routes = next_steps
        #print routes, grid_map
        
    return grid_map[end_pt]
    
def trace_routes(grid_width, grid_height):
    grid = build_grid(grid_width, grid_height)
    start_pt = (0, grid_height)
    end_pt = (grid_width, 0)
    routes = deque([[start_pt]])
    
    while not all_routes_finished(routes, end_pt):
        route = routes.popleft()
        new_routes = extend_route(route, grid)
        routes.extend(new_routes)

    return routes

def extend_route(route, grid):
    """return list of routes on grid (moving only right or down)"""
    routes = []
    from_pt = route[-1]
    
    if can_move_right(grid, from_pt):
        new_route = route + [move_right(from_pt)]
        routes.append(new_route)
        
    if can_move_down(grid, from_pt):
        new_route = route + [move_down(from_pt)]
        routes.append(new_route)
        
    return routes

def next_steps(grid, pt):
    pts = []
    
    if can_move_right(grid, pt):
        pts.append(move_right(pt))
        
    if can_move_down(grid, pt):
        pts.append(move_down(pt))
        
    return pts

def can_move_right(grid, from_pt):
    next_pt = (from_pt[0]+1, from_pt[1])
    return next_pt in grid

def can_move_down(grid, from_pt):
    next_pt = (from_pt[0], from_pt[1]-1)
    return next_pt in grid

def move_right(from_pt):
    return (from_pt[0]+1, from_pt[1])
    
def move_down(from_pt):
    return (from_pt[0], from_pt[1]-1)

def all_routes_finished(routes, end_pt):
    for route in routes:
        if route[-1] != end_pt:
            return False
    return True 
    
def build_grid(width, height):
    grid = []
    
    for x in range(width+1):
        for y in range(height+1):
            grid.append((x,y))
            
    return grid
    

#
# Additional Tests
#
def test_grid():
    grid = build_grid(4,4)
    
    assert (0,0) in grid
    assert (4,4) in grid
    assert (4,5) not in grid
    assert_match(len(grid), 25)
    
    print "test_grid passed!"




#
# Main
#
if __name__ == '__main__':
    test_grid()
    test_case()
    print solution()
    